package com.longge;

import java.util.ArrayList;
import java.util.List;

public class PathSumII {

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        ArrayList<Integer> curList = new ArrayList<>();
        dfs(root,targetSum,curList);
        return ans;
    }

    private void dfs(TreeNode root, int targetSum, ArrayList<Integer> curList) {
        if (root==null){
           return;
        }
        curList.add(root.val);
        if (root.left==null&&root.right==null){
            if (curList.stream().mapToInt(Integer::valueOf).sum()==targetSum){
                ans.add(new ArrayList<>(curList));
            }
        }
        dfs(root.left,targetSum,curList);
        dfs(root.right,targetSum,curList);
        curList.remove(curList.size()-1);
    }
}
